Intersection of Two Arrays II
Leetcode #350 | Easy | Хэш-таблицы
Идея
В мапу записываем частоты первого. Идем по второму числу, если число есть в мапе - добавляем в результат, потом в мапе вычитаем 1 из количества
Big-O
- Время
O(N+M) - Память
O(min(N,M))
Код
class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
Map<Integer, Integer> map = new HashMap<>();
List<Integer> res = new ArrayList<>();
for (int n : nums1) map.put(n, map.getOrDefault(n, 0) + 1);
for (int n : nums2) {
if (map.getOrDefault(n, 0) > 0) {
res.add(n);
map.put(n, map.get(n) - 1);
}
}
int[] ans = new int[res.size()];
for (int i = 0; i < res.size(); i++) ans[i] = res.get(i);
return ans;
}
}